Алгоритъм за сортиране

Алгоритъм за сортиране е алгоритъм, който подрежда списък от елементи в определена последователност.^[1] Най-използваните подредби са числовите и лексикографските подредби. Ефективните алгоритми за сортиране са важни за оптимизацията на други алгоритми (например алгоритми за търсене, алгоритми за сливане и др.), който изискват входните данни да са сортирани в определена последователност. Често също така е полезно за конкатенизиране (сливане) на данни и за генериране на разбираеми за човек крайни резултати. Формално казано, изходният резултат от алгоритъма за сортиране трябва да задоволява две условия:

Изходният резултат е в ненамаляваща последователност (всеки елемент не трябва да е по-малък от предходните на базата на очакваната обща подредба);
Изходният резултат е пермутация (пренаредба) на входните елементи.

От раждането на компютърните науки, алгоритмите за сортиране са били в процес на разработка и развитие. Ефективното решаване на проблеми, които са на пръв поглед прости и познати, се оказва доста по-сложна и трудоемка задача. Например методът на мехурчето за пръв път е бил анализиран през 1956 година. Въпреки че мнозина са смятали проблема за сортиране за решен, нови по-ефективни алгоритми са продължавали да се откриват (например методът на библиотечното сортиране е бил публикуван за първи път през 2006 година). Алгоритмите за сортиране често се представят в началните класове по компютърни науки, където изобилието от алгоритми за решаването на един проблем елегантно показва разнообразието от ключови алгоритмични концепции, като например голямото О, разделяй и владей, структурни данни, случайни алгоритми, най-добър, най-лош и среден случай, компромис време-памет, горна и долна граница.

Класификация

Сортиращите алгоритми често се класифицират по:

Изчислителна сложност при сравняване на елементите (най-лош, среден и най-добър случай) при сравняване на елементи в списък от (n) елемента. Добър пример за серийно сортиране O(n log n), за паралелно сортиране O(log² n), и за лошо сортиране O(n²). Вижте нотацията на голямото О. Идеалният резултат при серийно сортиране е O(n), но това не е постижимо в повечето случаи. Оптималното паралелно сортиране е O(log n). Сравняващо-базираните алгоритми за сортиране, които оценяват списъка с елементи на базата на абстрактна ключова операция за сравнение, имат нужда от поне O(n log n) сравнения при сортиране
Използвана памет (и други компютърни ресурси)
Рекурсивни. Някои алгоритми са или рекурсивни, или не-рекурсивни, докато други могат да съчетават и двата вида като например (алгоритъмът за сортиране чрез сливане)
Стабилност
Дали са сравняващи алгоритми – сравняващите алгоритми сравняват два елемента с оператор за сравнение
Адаптиращи се алгоритми

Стабилност

Когато се сортират някакви данни, само част от техните признаци се анализират при тяхното подреждане. Примерът от дясно показва, че картите са сортирани по ранг (от 2 до 7), а техният цвят се игнорира. От това следва, че крайният резултат може да бъде различен. Алгоритмите за стабилно сортиране използват следното правило: ако два елемента при сравнение са еднакви (като например двете петици), то тяхната първоначална подредба ще бъде съхранена, така че ако едната от тях е преди другата в началната подредба, то тя ще бъде първа и в крайния резултат.

Когато еднаквите елементи са неразличими, като целочислените числа или други по-общи данни където всеки елемент е уникален по всичките си признаци, стабилността не е проблем. Стабилността не е проблем и когато всички елементи са различни.

Нестабилното сортиране може да бъде превърнато в стабилно чрез допълнително разширяване логиката за сравняване, така че сравняването на два елемента, които по един признак са еднакви, да бъдат различени по един или повече други признаци. Това допълнително разширение обаче води до нуждата от допълнително време и памет.

Един подход за стабилно сортиращи алгоритми е сортиране на списъци по първичен и вторичен ключ. Например, при сортиране на група от карти първият ключ ще бъде техният ранг (2,3,4, …, А), а вторият техният цвят (♣,♦,♥, ♠). Това може да стане с един и същ алгоритъм за сортиране, но с различен ключ за сравняване:

Размяната на ключовете може обаче да доведе до нестабилно сортиране. Отново примера с картите – ако първо се сравнява по цвят, а после по ранг, не винаги крайният резултат ще бъде един и същ.

Сравнение на алгоритмите

В таблицата, n е номерата на записи, които трябва да се сортират. Колоните „Средно“ и „Най-лошо“ показват времевата сложност (също така наречена изчислителна сложност) на всеки от алгоритмите. Колоната „Памет“ е за паметта, която се изисква, както допълнение към базовата памет (съхраняваща списъка с елементи), необходима за извършване операции и преподредба на елементите при съответния алгоритъм за сортиране. Всички по-долу са сравняващи сортиращи алгоритми и те не могат да бъдат с по-добра производителност от O(n log n) в сродения си или най-лошия си случай. Времето за изпълнение и паметта използвана от алгоритмите може да бъде измерена чрез различни нотации като например – тета, омега, голямото-О, малкото-О и други. Паметта и времето за изпълнение по-долу е приложимо за всичките видове нотации.

Сортиране чрез сравнение
Име	Най-добър	Среден	Най-лош	Памет	Стабилен	Метод	Бележки
Бързо сортиране	20 ${\mathcal {}}n\log n$	20 ${\mathcal {}}n\log n$	25 ${\mathcal {}}n^{2}$	05 ${\mathcal {}}\log n$ при среден, $n$ в най-лошия случай	Зависи	разделяне	Бързото сортиране обикновено се прави с O(log(n)) стеково пространство.^[2]^[3] Повечето му имплементации са нестабилни, като при реализиране на стабилно сортиране както сложността на алгоритъма, така и нуждата от допълнителна памет се увеличава
Сортиране чрез сливане	20 ${\mathcal {}}{n\log n}$	20 ${\mathcal {}}{n\log n}$	20 ${\mathcal {}}{n\log n}$	15 Зависи; в най-лошия случай е ${\mathcal {}}n$	Да	сливане	Сортиране чрез сливане е високо паралелистичен (до O(log(n))
Пирамидално сортиране	20 ${\mathcal {}}{n\log n}$	20 ${\mathcal {}}{n\log n}$	20 ${\mathcal {}}{n\log n}$	00 ${\mathcal {}}{1}$	Не	селекция
Сортиране чрез вмъкване	15 ${\mathcal {}}n$	25 ${\mathcal {}}n^{2}$	25 ${\mathcal {}}n^{2}$	00 ${\mathcal {}}{1}$	Да	вмъкване	O(n + d), където d е броят на преместванията
Сортиране чрез пряка селекция	25 ${\mathcal {}}n^{2}$	25 ${\mathcal {}}n^{2}$	25 ${\mathcal {}}n^{2}$	00 ${\mathcal {}}{1}$	Не	селективно	Стабилно с O(n) допълнително пространство или с използване на допълнителни списъци.^[4]
Шел сортиране	15 ${\mathcal {}}n$	23 ${\mathcal {}}n(\log n)^{2}$ или ${\mathcal {}}n^{3/2}$	23 Зависи от разстоянието в последователността; най-добрият известен случай е ${\mathcal {}}n(\log n)^{2}$	00 ${\mathcal {}}1$	Не	вмъкване	Малък блок код, без Small code size, не използва стек на извикванията, разумно бърз, полезен, където паметта е приоритет, като например вградените и по-старите майнфрейм приложения
Метод на мехурчето	15 ${\mathcal {}}n$	25 ${\mathcal {}}n^{2}$	25 ${\mathcal {}}n^{2}$	00 ${\mathcal {}}{1}$	Да	Размяна	Кратък код
Сортиране с помощта на двоично дърво	15 ${\mathcal {}}n$	20 ${\mathcal {}}{n\log n}$	20 ${\mathcal {}}{n\log n}$	15 ${\mathcal {}}n$	Да	Вмъкване	Когато се използват алгоритъм за търсене в балансирано дърво

Представяне на по-популярните алгоритми за сортиране

Метод на мехурчето

Основна статия: Метод на мехурчето

Методът на мехурчето (на английски: Bubble sort) е прост сортиращ алгоритъм. Алгоритъмът започва в началото на сортиращия се списък. Той сравнява първия и втория елемент, и ако първият е по-голям от втория, ги разменя. Продължава да прави с това с всички съседни двойки елементи до края на сортиращия се списък. След това повтаря същото действие още толкова пъти, докато накрая при обхождането на целия списък не е направено нито една размяна на два съседни елемента. Средният и най-лош случай на този алгоритъм е O(n²) и не се използва за сортиране на големи неподредени множества от данни. Методът на мехурчето може да се използва за малки множества или за множества, където има елементи близо до очакваното си място. Например, ако някой елемент не е на мястото си, на разстояние един елемент (например 112 и 111), методът на мехурчето ще обходи един път множеството и ще направи размяната, а на второто обхождане няма да направи размяна и ще завърши сортирането, и това ще отнеме само 2n.

Сортиране чрез пряка селекция

Основна статия: Сортиране чрез пряка селекция

Алгоритъмът за сортиране чрез пряка селекция (на английски: Selection sort) е неефективен с изчислителна сложност On². Подобен алгоритъм, който има по-добра производителност, е алгоритъмът за сортиране чрез вмъкване. Сортирането чрез пряка селекция впечатлява с простотата си, а също така в дадени ситуации има предимства пред някои сложни алгоритми.

Алгоритъмът намира най-малкия елемент в списъка и го разменя с първия елемент. След това търси втория най-малък и го поставя на второ място. Действието се повтаря, докато се стигне до края на списъка. При този алгоритъм не се правят повече от n размени. Този алгоритъм е полезен в случаи, когато размяната на елементи е тежка операция и трябва да се минимизира.

Сортиране чрез вмъкване

Основна статия: Сортиране чрез вмъкване

Сортирането чрез вмъкване (на английски: Insertion sort) е прост алгоритъм, който е относително ефективен при малки и почти сортирани списъци, като често се използва в комбинация с по-усъвършенствани алгоритми. Алгоритъмът работи като взема всеки елемент един по-един от списъка и го вмъква на съответното си място в нов сортиран списък. При сортиране на масиви елементите могат да споделят базовата памет (пространство), но се извършват прекалено много премествания на елементи което е скъпа операция. Шел сортирането е по-усъвършенстваният вариант за по-големи списъци.

Шел сортиране

Основна статия: Шел сортиране

Шел сортирането е открито от Доналд Шел през 1959 година. То подобрява метода на мехурчето и сортирането чрез вмъкване чрез преместването на елементите през повече от една позиция в даден момент. Може да бъде описано като нареждане на последователни елементи в двумерен масив и след това сортирането на колоните на масива чрез сортиране чрез вмъкване

Сортиране чрез сливане

Основна статия: Сортиране чрез сливане

Сортирането чрез сливане (на английски: Merge sort) използва принципа на сливане на вече сортирани списъци. Започва с обединяването на всяка двойка елементи (например 1 и 2, после 3 и 4 ...) и ги разменя ако първата двойка трябва да е след втората. След това слива всички списъци от два елемента в списъци от четири, отново ги пренарежда и ги слива в списъци от осем и т.н., докато останат само два списъка, които се сливат последно за да приключи сортирането. Този алгоритъм се представя добре при списъци с големи мащаби и при най-лош случай има ефективност O(n log n). Също така се прилага лесно както за масиви, така и за списъци, стига да предоставя последователен достъп към елементите. Минус е обаче ефективността на памет O(n), както и прекалено многото използване на прости операции като присвояване и копиране.

Пирамидално сортиране

Основна статия: Пирамидално сортиране

Пирамидалното сортиране(на английски: Heapsort) е много по-ефективно от Сортирането чрез пряка селекция. Този вид сортиране на принципа на определяне на най-малкия и най-големия елемент в списъка и поставянето им в двата края, след което прави същото и за останалата част на несортирания списък. За да се реализира този алгоритъм, несортираният списък се представя като специална структура от данни heap, наречена Двоично дърво. Веднъж представен списъкът по този начин се гарантира, че коренът на дървото има най-големия (или най-малкия) елемент от списъка. Когато този елемент се вземе и постави в началото на сортирания списък, останалите елементи се пренареждат отново така че да коренът отново да бъде най-големият (или най-малкият) елемент от останалия несортиран списък. Използвайки хийпът намирането на най-големия елемент отнема O(log n) време, вместо O(n) при линейно търсене. Това позволява пирамидалното сортиране да има времева ефективност O(n log n), както и при най-лош сценарий.

Сортиране чрез броене

Основна статия: Сортиране чрез броене

Сортирането чрез броене е алгоритъм за сортиране на група от обекти спрямо техните ключове, които са малки цели числа; това е алгоритъм за сортиране на цели числа. Алгоритъмът се изпълнява, като брои обектите с различни стойности на ключа, и използвайки аритметика за тези числа за определяне на позициите на всяка ключова стойност в изходната поредица. Времето за изпълнение е линейно в рамките на броя на елементите и разликата между максималната и минималната ключова стойност, така че е подходящ само за директна употреба в случаите, когато разликата в ключовете не е значително по-голяма от броя на елементите.

Бързо сортиране

Основна статия: Бързо сортиране

Алгоритъмът за бързо сортиране (на английски: Quicksort) е един от най-добрите алгоритми за търсене на голям брой елементи. Нарича се още алгоритъмът на Хор, заради името на човека, който го е измислил – Тони Хор. Този алгоритъм прави O(n log n) сравнения за да сортира n на брой елемента. В практиката алгоритъмът за бързо сортиране е по-бърз от другите O(n log n) алгоритми. Неговата имплементация се извършва с рекурсия.

Bucket сортиране

Основна статия: Bucket сортиране

Bucket sort, или bin sort, е сортиращ алгоритъм, който работи чрез разделяне на един масив в определен брой контейнери. След това всеки „контейнер“ се сортира индивидуално, или чрез използване на различни сортиращи алгоритми, или чрез рекурсивно прилагане на bucket сортиране. Bucket сортиране е обобщаващ на pigeonhole sort, алгоритъм. Пресмятането на изчислителната сложност включва броя на използваните „контейнери“. Bucket sort може да се изпълнява с линейно време – (Θ(n)). Всяка кофа трябва да съдържа или един елемент, или да се сортира.

Сортиране по метода на гребена

Основна статия: Сортиране по метода на гребена

Сортирането по метода на гребена е прост алгоритъм за сортиране, първоначално разработен от Владимир Добошевич през 1980 г. По-късно алгоритъмът е преоткрит от Стефан Ласи и Ричард Бокс през 1991 г. Алгоритъмът на гребена подобрява метода на мехурчето.

Модели за използване на паметта и сортиране чрез индекси

Когато размерът на сортиращия масив започне да доближава или превишава наличната основна памет и алгоритъмът започне да се изпълнява по-бавно поради причината, че започва да използва виртуалната памет намираща се на твърдия диск, моделите за организиране на паметта започват да играят по-голяма роля, а алгоритмите за сортиране които на пръв поглед работят по-бързо (когато масивите им се побират в оперативната памет) започват да се изпълняват много по-бавно. При такива сценарии броят на сравнения става относително по-маловажен, а броят четене и писане в оперативната памет и диска става по-значителен при производителността на даден алгоритъм.

Например популярният алгоритъм за сортиране бързо сортиране предлага достатъчно добра производителност при налична оперативна памет, но заради рекурсивната си природа този алгоритъм прави прекалено много копия на сортиращия се масив и когато излезе извън границите на оперативната си памет и започне да се използва твърдия диск, производителността му рязко спада.

Един начин да се заобиколи този проблем, който работи добре при по-сложните записи (като например релационните бази данни), е списъците да се сортират по относително малки по обем ключове (индекси), вместо целите записи. След това с едно обхождане могат да се сортират всички записи на базата на техните индекси, въпреки че това не е необходимо тъй като индексите сочат към съответните си записи. Такова сортиране се нарича още така „тагово сортиране“.

Друг подход за решаване на проблема с паметта е да се комбинират няколко сортиращи алгоритъма така, че да се използват само силните им страни.

Външни препратки

Книгата „Програмиране = ++Алгоритми“ онлайн, 2012. Линкът е посетен на 07.03.2020 г.

Източници

↑ [Наков, П., Добриков, П. Програмиране = ++Алгоритми, С., 2003, стр. 199]
↑ Sedgewick, Robert. Algorithms In C: Fundamentals, Data Structures, Sorting, Searching, Parts 1 – 4. 3. Pearson Education, 1 September 1998. ISBN 978-81-317-1291-7. Посетен на 27 ноември 2012 г.
↑ Sedgewick, R. Implementing Quicksort programs // Communications of the ACM 21 (10). 1978. DOI:10.1145/359619.359631. с. 847 – 857.
↑ SELECTION SORT (Java, C++) – Algorithms and Data Structures // Посетен на 14 април 2018 г.

[1] [Наков, П., Добриков, П. Програмиране = ++Алгоритми, С., 2003, стр. 199]

[2] Sedgewick, Robert. Algorithms In C: Fundamentals, Data Structures, Sorting, Searching, Parts 1 – 4. 3. Pearson Education, 1 September 1998. ISBN 978-81-317-1291-7. Посетен на 27 ноември 2012 г.

[sedgewickQsortPaper-3] Sedgewick, R. Implementing Quicksort programs // Communications of the ACM 21 (10). 1978. DOI:10.1145/359619.359631. с. 847 – 857.

[4] SELECTION SORT (Java, C++) – Algorithms and Data Structures // Посетен на 14 април 2018 г.

[1]

[2]

[3]

[4]